Minibus in Mendeleevo city
moves according to the route from the bus stop number 1 to the bus stop number m. The driver stops at the station only
if at least one of the passengers in the cabin wants to get out. At the same
time all the passengers waiting for a minibus at this stop, sit in it (number
of seats is unlimited). As the bus starts moving from the stop number 1,
all passengers at it just sit down in a minibus.
Given the list of
passengers, determine the list of stations where the bus stops. It is
guaranteed that at least one passenger of minibus waits at the bus stop
number 1.
Input. First line contains two
positive integers n, m
(1 ≤ n ≤ 105,
1 ≤ m ≤ 109) – the number of
passengers and bus stops. Each of the next n lines contains two positive
integers li – the number
of bus stop where the i-th passenger waits
for minibus, ri – the number
of bus stop where the i-th
passenger goes out (1 ≤ li
< ri ≤ m).
Output. Print in the first line the
number of bus stops k where the minibus will stop. Then print k lines – the numbers
of these bus stops in increasing order.
Sample input |
Sample output |
6 11 1 4 2 3 4 5 2 5 4 7 4 10 |
5 1 4 5 7 10 |
graphs
Construct a
directed graph, which
vertices are stops,
and the edges are passengers connecting the vertices li and ri. Since the number of vertices in the graph (stops) is m ≤ 109, and the graph
is sparse (the number of edges is n ≤
105), then the adjacency list g
is given by the
structure map<int,vector<int> > g – each vertex is
assigned an adjacency list stored in the vector. To remember the visited vertices, we’ll use the set set<int> as the used structure.
Run the depth-first
search from the vertex
1. The vertices that will be visited (that will be added
to used) are the numbers of stops where the minibus
will stop.
Declare an adjacency list of the graph g, as well as
the set of visited vertices used.
set<int> used;
set<int>::iterator iter;
map<int,vector<int>
> g;
Depth first search from the vertex v.
void
dfs(int v)
{
Mark the vertex v to be used.
used.insert(v);
Iterate the vertices, adjacent to v.
for(int i = 0; i < g[v].size(); i++)
{
Graph contains the edge (v, to).
int to =
g[v][i];
If the vertex to is not visited, run depth first search from to.
if(used.find(to)
== used.end()) dfs(to);
}
}
The main part of the program. Read the input data, construct the graph.
scanf("%d %d",&n,&m);
for(i
= 0; i < n; ++i)
{
scanf("%d
%d",&x,&y);
g[x].push_back(y);
}
Run depth first search from the vertex 1.
dfs(1);
Print the list of visited
vertices – the numbers of stops where the minibus will stop.
printf("%d\n",used.size());
for(iter
= used.begin(); iter != used.end(); iter++)
printf("%d\n",*iter);